/**
 * @author 03010570
 * @date 2020/06/10
 * describe:
 * <p>
 * 1、冒泡排序  O(n^2)
 * 2、插入排序  O(n^2)
 * 3、选择排序  O(n^2)
 * <p>
 * 4、快速排序  O(nlogn)
 * 5、归并排序  O(nlogn)
 * <p>
 * 6、桶排序    O(n)
 * 7、计数排序  O(n)
 * 8、基数排序  O(n)
 */
public class LeetCode_Sort {

    public static void main(String[] args) {
        int[] ints = {4, 5, 6, 3, 2, 1};
//        bubbleSort2(ints);
//        insertSort2(ints);
        selectSort(ints);
        for (int anInt : ints) {
            System.out.print(anInt);
        }
    }

    /**
     * 1、冒泡排序
     */
    public static void bubbleSort(int[] ints) {
        for (int i = 0; i < ints.length; i++) {
            for (int j = 0; j < ints.length - i - 1; j++) {
                if (ints[j] > ints[j + 1]) {
                    int temp = ints[j + 1];
                    ints[j + 1] = ints[j];
                    ints[j] = temp;
                }
            }
        }
    }

    /**
     * 2、插入排序
     */
    public static void insertSort(int[] ints) {
        int length = ints.length;
        for (int i = 1; i < length; i++) {
            int value = ints[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                if (ints[j] > value) {
                    ints[j + 1] = ints[j];
                } else {
                    break;
                }
            }
            ints[j + 1] = value;
        }

    }

    /**
     * 1、冒泡排序
     */
    public static void bubbleSort2(int[] ints) {
        long start = System.currentTimeMillis();
        int length = ints.length;
        for (int i = 0; i < length; i++) {
            boolean flag = false;
            for (int j = 0; j < length - 1; j++) {
                if (ints[j] > ints[j + 1]) {
                    int temp = ints[j];
                    ints[j] = ints[j + 1];
                    ints[j + 1] = temp;
                    flag = true;
                }
            }
            if (flag) {
                break;
            }
        }
        long end = System.currentTimeMillis();
        System.out.println(start);
        System.out.println(end);
        System.out.println(end - start);
    }

    /**
     * 2、插入排序
     */
    public static void insertSort2(int[] ints) {
        int length = ints.length;
        for (int i = 0; i < length; i++) {
            int value = ints[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                if (ints[j] > value) {
                    ints[j + 1] = ints[j];
                } else {
                    break;
                }
            }
            ints[j + 1] = value;

        }
    }

    /**
     * 3、选择排序
     */
    public static void selectSort(int[] ints) {
        int length = ints.length;
        for (int i = 0; i < length - 2; i++) {
            int min = Integer.MAX_VALUE;
            int j = length-1;
            int index=length-1;
            for (; j >i; j--) {
                if (ints[j] < min) {
                    min = ints[j];
                    index=j;
                }
            }
            ints[index] = ints[i];
            ints[i] = min;
        }
    }

    /**
     * 4、快速排序
     */

    /**
     * 5、归并排序
     */
}
























